/*
A sprite polygonal contour extractor.
Copyright (C) 2009-2010  Julien CLEMENT (andematunum@gmail.com)

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "sprite_contour.h"
#include <iostream>
using namespace std;

namespace SpriteContourExtractor {

static bool check_inputs (const void* pixels, uint8_t bpp) {
	if (pixels == NULL) {
		return false;
	}
	if ((bpp != 8) &&
			(bpp != 16) &&
			// NOT YET SUPPORTED
			//(bpp != 24) &&
			(bpp != 32)) {
		return false;
	}
	return true;
}

// Generic template for generating functions
// for reading a pointer to an image data,
// depending on the image depth (bits per pixel),
// and checking if the point is equal to the
// colorkey or not.
#define IMPL_PIXOFF(bpp) \
static bool pixoff_##bpp (const void* pixels, \
					   					    uint32_t colorkey, uint16_t w, uint16_t x, uint16_t y) { \
	uint##bpp##_t* data = (uint##bpp##_t *)pixels; \
	uint##bpp##_t pixel = *(data + (y*w+x)); \
	return (pixel == (uint##bpp##_t)colorkey); \
}
// Implement image readers for each supported depth.
IMPL_PIXOFF(8)
IMPL_PIXOFF(16)
IMPL_PIXOFF(32)
// Neighborhood iterator:
// This is the very core structure of the algorithm.
class PointNeighborItr {
	public:
	PointNeighborItr(const Point2d& start_pt, bool orientation, uint16_t indice)
		: point_(start_pt), neigh_(start_pt), nb_of_itr_(0),
			indice_(indice) {
		if (indice == UINT16_MAX) {
			indice_ = (orientation) ? (0) : (4);
		}
		orientation_ = (orientation) ? (+1) : (-1);
	}
	bool more() {
		return (nb_of_itr_ < 7);
	}
	void next() {
		indice_ = get_indice_(indice_);
		nb_of_itr_ ++;
	}
	Point2d cur () {
		neigh_.x = point_.x + offx_[indice_];
		neigh_.y = point_.y + offy_[indice_];
		return neigh_;
	}
	const uint16_t next_indice () {
		#ifdef DEBUG
		cout << "*** DEBUG: Current indice: " << indice_ << endl;
		cout << "***        Reciprocal indice: " << indice_in_neigh_[indice_] << endl;
		#endif
		return indice_in_neigh_[get_indice_(indice_)];
	}
	const uint16_t indice () {
		return indice_;
	}
	private:
		uint16_t get_indice_ (uint16_t indice) {
			if ((int16_t)indice + orientation_ < 0) {
				return 8 + orientation_;
			}
			else {
				return (indice + orientation_) % 8;
			}
		}
	private:
		const Point2d& point_;
		Point2d neigh_;
		uint16_t nb_of_itr_;
		int16_t orientation_;
		uint16_t indice_;
		static const uint16_t offx_[8];
		static const uint16_t offy_[8];
		static const uint16_t indice_in_neigh_[8];
};

const uint16_t PointNeighborItr::offx_[8] = {
	1,1,0,-1,-1,-1,0,1
};
const uint16_t PointNeighborItr::offy_[8] = {
	0,1,1,1,0,-1,-1,-1
};
const uint16_t PointNeighborItr::indice_in_neigh_[8] = {
	4,5,6,7,0,1,2,3
};

struct Vector2d {
  int16_t x;
  int16_t y;
  Vector2d(int16_t xx, int16_t yy)
    : x(xx), y(yy) {
  }
	Vector2d(const Vector2d& other) {
		x = other.x;
		y = other.y;
	}
	Vector2d& operator= (const Vector2d& other) {
		x = other.x;
		y = other.y;
		return *this;
	}
};


void extract_contour (const void* pixels,
											const Point2d& size,
											uint8_t bits_per_pixel,
											uint32_t colorkey,
											bool orientation,
											list<Point2d*>& contour) {
	
	if (!check_inputs (pixels, bits_per_pixel)) {
		return;
	}
	// Reading function pointer.
	bool (*pixoff)(const void* pixels, uint32_t colorkey,
		   					 uint16_t w, uint16_t x, uint16_t y) = NULL;
	// Assign the appropriate image reading function
	switch (bits_per_pixel) {
		case 8:
			pixoff = &pixoff_8;
			break;
		case 16:
			pixoff = &pixoff_16;
			break;
		case 32:
			pixoff = &pixoff_32;
			break;
		default:
			return;
	}
	// Current pixel
	Point2d point(0,0);
	// Use scanline to find the first point
	bool found = false;
	for (point.y = 0; point.y < size.y; point.y++) {
		for (point.x = 0; point.x < size.x; point.x++) {
			if (!pixoff(pixels,colorkey,size.x,point.x,point.y)) {
				found = true;
				break;
			}
		}
		if (found) {
			break;
		}
	}
	// The image was empty
	if (!found) {
		return;
	}

	// Remember start point to know
	// when we're finished
	Point2d start_point = point;
	#ifdef DEBUG
	cout << "*** DEBUG: Start point found: " << point.x << "," << point.y << endl;
	#endif

	// "Micro Jarvis" progression loop
	// Current slope initialized to (2,2),
	// which is a no data value for the slope.
	// This to force the first point to be added
	// and the first slope to be calculated.
	Vector2d slope(2,2);
	// Added whenever the slope changes
	Point2d prev_point(point);
	// Becomes true when:
	// - We looped back to the first point: valid case
	// - No neighbor was found: unexpected error
	bool finished = false;
	// Add the first point to the contour
	// contour.push_back(new Point2d(point.x,point.y));
	// Indice from which we read the neighborhood
	uint16_t indice = UINT16_MAX;
	// Remember the previous indice. If the same,
	// then we have a non closed contour.
	uint16_t prev_indice = UINT16_MAX;
	#ifdef DEBUG
	int npoints = 0;
	#endif

	// Loop
	while (!finished) {
		// Examine neighborhood
		bool found = false;
		for (PointNeighborItr i_pt(point, orientation, indice);
				 i_pt.more();
				 i_pt.next()) {
			Point2d pt = i_pt.cur();
			// Clipping: exclude points out of the image
			if ((pt.x == UINT16_MAX) || (pt.x >= size.x) ||
			    (pt.y == UINT16_MAX) || (pt.y >= size.y)) {
					continue;
			}
			#ifdef DEBUG
			cout << "*** DEBUG: Test point at " << pt.x << "," << pt.y << endl;
			#endif
			if (!pixoff(pixels,colorkey,size.x,pt.x,pt.y)) {
				Vector2d new_slope(pt.x-point.x, pt.y-point.y);
				if ((new_slope.x != slope.x) || (new_slope.y != slope.y)) {
					slope = new_slope;
					//contour.push_back(new Point2d(pt.x,pt.y));
					contour.push_back(new Point2d(prev_point));
					#ifdef DEBUG
					cout << "***DEBUG: New point found: " << pt.x << "," << pt.y << endl;
					cout << "          New slope:       " << slope.x << "," << slope.y << endl;
					#endif
				}
				prev_point = pt;
				point = pt;
				indice = i_pt.next_indice();
				// Detect unclosed contour
				if (i_pt.indice() == prev_indice) {
					cout << "*** ERROR: Unclosed contour." << endl;
					break;
				}
				prev_indice = indice;
				#ifdef DEBUG
				cout << "Next indice: " << indice << endl;
				npoints++;
				if (npoints == NPOINTS) {
					return;
				}
				#endif
				// Detect when we've finished the contour
				// (start point found again)
				if (pt == start_point) {
					finished = true;
					break;
				}
				else {
			  	found = true;
				  break;
				}
			}
			
		} // end for each neighbor
		if (finished) {
			return;
		}
		// Something went wrong
		if (!found) {
			cerr << "*** ERROR: Incorrect contour." << endl;
			return;
		}
		
	}
}

/*
	// Pixel reading offsets.
	uint16_t left, right, up, down;
	// Remember previous offsets to avoid extra points on the same line.
	uint16_t left_last, right_last, up_last, down_last;
	// Polylines.
	list<Point2d*> left_chain, right_chain, up_chain, down_chain;
	// Reading function pointer.
	bool (*pixoff)(const void* pixels, uint32_t colorkey,
								 uint16_t w, uint16_t x, uint16_t y) = NULL;

	// Assign the appropriate image reading function
	switch (bits_per_pixel) {
		case 8:
			pixoff = &pixoff_8;
			break;
		case 16:
			pixoff = &pixoff_16;
			break;
		case 32:
			pixoff = &pixoff_32;
			break;
		default:
			return;
	}

	// Horizontal scanline.
	for (uint16_t y = 0; y < size.y; y++) {
		left = 0;
		right = size.x - 1;
		// Left chain.
		while (pixoff(pixels,colorkey,size.x,left,y)) {
			left++;
		}
		if (y == 0) {
			left_last = left;
		}
		else {
			// Insert a point only if it is not at the same x.
			if (left != left_last) {
				left_chain.push_back(new Point2d(left,y));
				left_last = left;
			}
		}
		// Right chain.
		while (pixoff(pixels,colorkey,size.x,right,y)) {
			right--;
		}
		if (y == 0) {
			right_last = right;
		}
		else {
			// Insert a point only if it is not at the same x.
			if (right != right_last) {
				right_chain.push_back(new Point2d(right,y));
				right_last = right;
			}
		}
	} // End horizontal scanline.

	// Vertical scanline.
	for (uint16_t x = 0; x < size.x; x++) {
		up = 0;
		down = size.y - 1;
		// Left chain.
		while (pixoff(pixels,colorkey,size.x,x,up)) {
			up++;
		}
		if (x == 0) {
			up_last = up;
		}
		else {
			// Insert a point only if it is not at the same y.
			if (up != up_last) {
				up_chain.push_back(new Point2d(x,up));
				up_last = up;
			}
		}
		// Right chain.
		while (pixoff(pixels,colorkey,size.x,x,down)) {
			down--;
		}
		if (x == 0) {
			down_last = down;
		}
		else {
			// Insert a point only if it is not at the same y.
			if (down != down_last) {
				down_chain.push_back(new Point2d(x,down));
				down_last = down;
			}
		}
	} // End vertical scanline.
	// Build polygon by sticking each polyline in the
	// appropriate order to match the expected orientation.
	// The 'splice' technic appends the left list to the
	// host list, and empties the left list.
	// Clockwise.
	if (orientation) {
		contour.splice(contour.end(), left_chain);
		contour.splice(contour.end(), down_chain);
		contour.splice(contour.end(), right_chain);
		contour.splice(contour.end(), up_chain);
	}
	// Counter clock-wise.
	else {
		contour.splice(contour.end(), left_chain);
		contour.splice(contour.end(), up_chain);
		contour.splice(contour.end(), right_chain);
		contour.splice(contour.end(), down_chain);
	}
}
*/
void extract_contour_convex (const void* pixels,
														 const Point2d& size,
														 uint8_t bits_per_pixel,
														 uint32_t colorkey,
														 bool orientation,
														 list<Point2d*>& contour) {
	if (!check_inputs (pixels, bits_per_pixel)) {
		return;
	}
}

#ifdef _OPENMP
/**
	* Extract the polygonal contour.
	* The output polygon may be convex or not.
	* This version is parallelized with OpenMP.
	*/
void extract_contour_omp (const void* pixels,
													const Point2d& size,
													uint8_t bits_per_pixel,
													uint32_t colorkey,
													bool orientation,
													list<Point2d*>& contour);
/**
	* Extract the polygonal contour.
	* The output polygon is convex.
	* This version is parallelized with OpenMP.
	*/
void extract_contour_convex_omp (const void* pixels,
																 const Point2d& size,
																 uint8_t bits_per_pixel,
																 uint32_t colorkey,
																 bool orientation,
																 list<Point2d*>& contour);
#endif

}

